home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / NTUMIN10.ARJ / SSM.C < prev    next >
C/C++ Source or Header  |  1992-03-12  |  5KB  |  154 lines
  1. /****************************************************************************
  2. *
  3. *       Program Name : SSM.C
  4.  *
  5.  *    Written By : Eng-Huat Ong and Kian-Mong Low.
  6. *
  7. *       This program generates the Subsumming Sum of Minterms (SSM) of the
  8. *       given CPT.
  9. *
  10. *    Returns pointer to an array consisting of :
  11. *        1.  no. of X's in the given CPT
  12. *        2.  all minterms covered by the CPT (SSM's)
  13.  *
  14.  * --------------------------------------------------------------------------
  15.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  16.  *    University.
  17.  *
  18.  *    You are free to use, copy and distribute this software and its
  19.  *    documentation providing that:
  20.  *
  21.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  22.  *
  23.  *        IT IS NOT MODIFIED IN ANY WAY.
  24.  *
  25.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  26.  *
  27.  *    This program is provided "AS IS" without any warranty, expressed or
  28.  *    implied, including but not limited to fitness for any particular
  29.  *    purpose.
  30.  *
  31.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  32.  *    appreciated. Please send to:
  33.  *
  34.  *        Boon-Tiong Tan or Othman Bin Ahmad
  35.  *        School of EEE
  36.  *        Nanyang Technological University
  37.  *        Nanyang Avenue
  38.  *        Singapore 2263
  39.  *        Republic of Singapore
  40. *
  41. ****************************************************************************/
  42.  
  43. #include  <stdio.h>
  44. #include  <stdlib.h>
  45. #include  <string.h>
  46.  
  47. unsigned char *ssm(d)
  48. unsigned char *d;
  49.  
  50. {
  51.    unsigned long  m, j, m_cnt, test, terms;
  52.    unsigned char  *e, *temp, *hold, *px;
  53.    unsigned char  nspm, i, k, x_count, cnt, n;
  54.  
  55.    n = strlen(d);                             /* no. of variables */
  56.    nspm = (n+7)/8;                            /* no. of bytes/minterm */
  57.  
  58.    temp = (unsigned char *) malloc(nspm+1);   /* temporary storage */
  59.    if (temp == 0)
  60.       {
  61.      printf("Out of memory -- SSM, *temp\n");
  62.      printf("Program terminated - 1\n");
  63.      exit(0);
  64.       }
  65.  
  66.    px = (unsigned char *) malloc(n+1);          /* position of X's in CPT */
  67.    if (px == 0)
  68.       {
  69.      printf("Out of memory -- SSM, *px\n");
  70.      printf("Program terminated - 2\n");
  71.      exit(0);
  72.       }
  73.  
  74.    /***
  75.     ***  GENERATE 1ST SSM TERM
  76.     ***/
  77.  
  78.    j = 0;
  79.    x_count = 0;                                     /* no. of X's in CPT */
  80.    m = 0;                                           /* no. of SSM terms */
  81.  
  82.    for (i=0; i<n; i++)                              /* obtain 1st SSM term */
  83.       {
  84.      if ((i%8) == 0 )
  85.         *(temp+(i/8)) = 0;                      /* reset temp to zero */
  86.      if (*(d+i) == 'X' | *(d+i) == 'x')         /* char in CPT is 'X' */
  87.         {
  88.            x_count++;                           /* no. of X's in CPT */
  89.            *(px + j++) = i;                     /* position of X's */
  90.            *(temp+(i/8)) = *(temp+(i/8)) | (0<<(i%8));
  91.         }
  92.      else if (*(d+i) == '0')                     /* char in CPT is '0' */
  93.         *(temp+(i/8)) = *(temp+(i/8)) | (0<<(i%8));
  94.      else                                        /* char in CPT is '1' */
  95.         *(temp+(i/8)) = *(temp+(i/8)) | (1<<(i%8));
  96.       }
  97.  
  98.    e = (unsigned char *) malloc(4+nspm*topow(x_count));  /* space for all SSM's */
  99.    if (e == 0)
  100.       {
  101.      printf("Out of memory -- SSM, *e\n");
  102.      printf("Program terminated - 3\n");
  103.      exit(0);
  104.       }
  105.  
  106.    *e = n;                                   /* no. of variables */
  107.    *(e+3) = nspm;                            /* no. of bytes/minterm */
  108.  
  109.    memcpy((e+4),temp,nspm);                  /* 1st SSM term */
  110.    m++;                                      /* no. of SSM terms */
  111.  
  112.    /***
  113.     ***  EXPAND ON 1ST SSM TERM TO GENERATE OTHER SSM TERMS
  114.     ***/
  115.  
  116.    hold = (unsigned char *) malloc(nspm+1);   /* working array */
  117.    if (hold==0)
  118.       {
  119.      printf("Out of memory -- SSM, *hold");
  120.      printf("Program terminated - 4\n");
  121.      exit(0);
  122.       }
  123.  
  124.    m_cnt = 0;                            /* counter */
  125.  
  126.    for (i=0; i<x_count; i++)             /* generate other SSM terms */
  127.       {
  128.      terms = topow(i);               /* no. of terms to generate */
  129.  
  130.      for (j=1; j<=terms; j++)
  131.         {
  132.            m_cnt++;                  /* determines whether addition is required */
  133.            memcpy(hold, temp, nspm);           /* put in working array */
  134.  
  135.            for (k=0; k<=i; k++)                /* no. of bits to check */
  136.           {
  137.              test = m_cnt & (1<<k);        /* addition required ? */
  138.              if (test != 0)                /* YES, add to working array */
  139.             *(hold + *(px+k)/8) = *(hold + *(px+k)/8) + topow(*(px+k)%8);
  140.           }
  141.  
  142.            memcpy((e+4+nspm*m), hold, nspm);      /* add SSM to e-array */
  143.            m++;                                   /* no. of SSM terms */
  144.         }
  145.       }
  146.  
  147.    free(temp);                  /* free pointers */
  148.    free(px);
  149.    free(hold);
  150.  
  151.    *(e+1) = x_count;            /* no. of X's in CPT */
  152.  
  153.    return(e);                   /* return SSM terms */
  154. }